package 动态规划.backageQuestion;

/**
 * 编辑距离问题
 *编辑距离（Edit Distance）问题是一个经典的动态规划问题，它衡量的是将一个字符串转换成另一个字符串所需要的最少操作次数。操作包括插入一个字符、删除一个字符和替换一个字符。
 *
 * 思路分析: （状态，状态转移方程，初始化，结果）
 * 1: 状态分析：使用i表示第一个数据，使用j表示第二个数据， 那么d[i][j]就可以表示这两个数组
 * 2：状态转移方程：
 *    每一位是否相等肯定是两种情况，相等和不等
 *    如果 i == j， 那么 d[i][j] = dp[i-1][j-1]
 *    如果 i != j, 那么根据题意，有三种情况,(取其中的最小值)
 *      1：插入一个字符： dp[i][j] = dp[i][j-1]+1
 *      2: 删除一个字符（）： dp[i][j] = dp[i-1][j]+1
 *      3：替换一个字符 (): dp[i][j] = dp[i-1][j-1]+1
 *
 *
 *  插入操作 (dp[i][j] = dp[i][j - 1] + 1)：
 * 当我们考虑插入操作时，我们假设为了将 word1 的前 i 个字符转换为 word2 的前 j-1 个字符，我们已经知道了最少操作数（dp[i][j - 1]）。
 * 接下来，为了匹配 word2 中的第 j 个字符，我们在 word1 的末尾插入一个与 word2[j] 相同的字符。
 * 这就增加了一个额外的操作（插入），因此操作总数变为 dp[i][j - 1] + 1。
 * 删除操作 (dp[i][j] = dp[i - 1][j] + 1)：
 *
 * 考虑删除操作，意味着为了将 word1 的前 i-1 个字符转换为 word2 的前 j 个字符，我们已经知道了最少操作数（dp[i - 1][j]）。
 * 然后，我们从 word1 中删除第 i 个字符，希望通过这样做，word1 的前 i-1 个字符将与 word2 的前 j 个字符对齐。
 * 删除操作将操作总数增加1，因此操作总数是 dp[i - 1][j] + 1。
 * 替换操作 (dp[i][j] = dp[i - 1][j - 1] + 1)：
 *
 * 替换操作考虑的是将 word1 的前 i-1 个字符转换为 word2 的前 j-1 个字符的最小操作数（dp[i - 1][j - 1]），然后将 word1 中的第 i 个字符替换为 word2 中的第 j 个字符。
 * 如果 word1[i] 与 word2[j] 不同，我们需要进行这样的替换操作以匹配两个字符串。
 * 替换操作将总操作数增加1，因此操作总数是 dp[i - 1][j - 1] + 1。
 * 通过比较这三种操作产生的操作次数，我们可以确定在位置 (i, j) 的最小编辑距离。
 * 3： 初始化：
 *  dp[i][0] = i;
 *  dp[0][j] = j;
   4: 结果:
    dp[i][j] ;
 * @Author lf
 * @Date 3/23/2024
 */
public class EditRange {
    public int minDistance(String word1, String word2) {
        int [][] dp = new int[word1.length()+1][word2.length()+1];
        // 初始化
        for (int i = 0; i <= word1.length() ; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.length() ; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= word1.length() ; i++) {
            for (int j = 1; j <= word2.length() ; j++) {
                // 数组比较从0位开始，切记
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(Math.min(dp[i][j-1]+1,dp[i-1][j]+1),dp[i-1][j-1]+1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

    public static void main(String[] args) {
        EditRange editRange = new EditRange();
        String word1 = "horse";
        String word2 = "ros";
        System.out.println("The minimum edit distance is: " + editRange.minDistance(word1, word2));

    }
}
